package newKe;

import java.util.HashMap;
import java.util.Map;

public class NC12 {
    /**
     * 重建二叉树（剑指offer7
     *
     * 给定节点数为 n 的二叉树的前序遍历和中序遍历结果，请重建出该二叉树并返回它的头结点。
     * 例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建出如下图所示。
     */

    /**
     * Definition for binary tree
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int x) { val = x; }
    }

    private Map<Integer, Integer> indexMap;

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        int n = preorder.length;
        // 构造哈希映射，帮助我们快速定位根节点
        this.indexMap = new HashMap<Integer, Integer>();
        for (int i = 0; i < n; i++) this.indexMap.put(inorder[i], i);
        return myBuildTree(preorder, inorder, 0, n - 1, 0, n - 1);
    }
    public TreeNode myBuildTree(int[] preorder, int[] inorder, int qianl, int qianr, int zhongl, int zhongr) {
        // 终止条件
        if (qianl > qianr) return null;
        // 前序遍历中的第一个节点就是根节点
        int rootValue = preorder[qianl];
        // 在中序遍历中定位根节点
        int rootIndex = indexMap.get(rootValue);
        // 先把根节点建立出来
        TreeNode root = new TreeNode(rootValue);
        // 递归地构造左子树，并连接到根节点
        // 先序遍历中「从 左边界+1 开始的 size_left_subtree」个元素就对应了中序遍历中「从 左边界 开始到 根节点定位-1」的元素
        root.left = myBuildTree(preorder, inorder, qianl + 1, qianl + rootIndex - zhongl, zhongl, rootIndex - 1);
        // 递归地构造右子树，并连接到根节点
        // 先序遍历中「从 左边界+1+左子树节点数目 开始到 右边界」的元素就对应了中序遍历中「从 根节点定位+1 到 右边界」的元素
        root.right = myBuildTree(preorder, inorder, qianl + rootIndex - zhongl + 1, qianr, rootIndex + 1, zhongr);
        return root;
    }
}
